<html>
<head>
  <title>递归算法</title>
  <basefont face="微软雅黑" size="2" />
  <meta http-equiv="Content-Type" content="text/html;charset=utf-8" />
  <meta name="exporter-version" content="Evernote Windows/307027 (zh-CN, DDL); Windows/6.1.0 (Win32);"/>
  <style>
    body, td {
      font-family: 微软雅黑;
      font-size: 10pt;
    }
  </style>
</head>
<body>
<a name="606"/>
<h1>递归算法</h1>

<div>
<span><div><font style="font-size: 18pt;"><span style="min-height: 18pt; font-size: 18pt; color: rgb(28, 51, 135); font-family: SimSun; font-weight: bold;">递归</span><span style="min-height: 18pt; font-size: 18pt; color: rgb(28, 51, 135); font-family: Calibri; font-weight: bold;">RECURSION</span></font></div><div><br/></div><div>目标：</div><div><ul><li>了解某些用其他方法难解的问题或许有简单的递归揭发</li><li>学会如何用递归的方式写程序</li><li>理解和运用递归的三大法则</li><li>了解递归是迭代（iteration）的一种形式</li><li>实现问题的递归描述</li><li>了解递归在计算机系统中如何实现</li></ul><div><br/></div></div><div><br/></div><div><span style="line-height: 1.45;">递归是一种解决问题的方法，它把一个问题分解为越来越小的子问题，直到问题的规模小到可以被很简单直接解决。通常为了达到分解问题的效果，递归过程中要引入一个调用自身的函数。</span></div><div><br/></div><div><span style="font-size: 16pt; color: rgb(173, 0, 0);">计算数字列表的和</span></div><div>迭代法：</div><div style="box-sizing: border-box; padding: 8px; font-size: 12px; border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.14902);"><div><span style="min-height: 12pt; font-size: 10pt; background-color: rgb(251, 250, 248); color: rgb(51, 51, 51); font-family: Calibri; font-weight: bold;">def list_sum(num_list):</span></div><div style="min-height: 12pt;"><span style="min-height: 12pt; font-size: 10pt; background-color: rgb(251, 250, 248); color: rgb(51, 51, 51); font-family: Calibri; font-weight: bold;">    the_sum = 0</span></div><div style="min-height: 12pt;"><span style="min-height: 12pt; font-size: 10pt; background-color: rgb(251, 250, 248); color: rgb(51, 51, 51); font-family: Calibri; font-weight: bold;">    for i in num_list:</span></div><div style="min-height: 12pt;"><span style="min-height: 12pt; font-size: 10pt; background-color: rgb(251, 250, 248); color: rgb(51, 51, 51); font-family: Calibri; font-weight: bold;">        the_sum = the_sum + i</span></div><div style="min-height: 12pt;"><span style="min-height: 12pt; font-size: 10pt; background-color: rgb(251, 250, 248); color: rgb(51, 51, 51); font-family: Calibri; font-weight: bold;">    return the_sum</span></div><div><span style="min-height: 12pt; font-size: 10pt; background-color: rgb(251, 250, 248); color: rgb(51, 51, 51); font-family: Calibri; font-weight: bold;">print(list_sum([1,3,5,7,9]))</span></div></div><div>现在，假设我们不能使用while循环或者for循环</div><div>加法是一个有两个参数——两个数字——的函数。为了将数字列表的问题重新定义为对两个参数求和的问题，我们可以利用全括号的表达式来重新表示列表，就像下面这种形式：</div><div>((((1+3)+5)+7)+9)</div><div><br/></div><div>递归法：</div><div style="box-sizing: border-box; padding: 8px; font-size: 12px; border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.14902);"><div><span style="font-size: 10pt; background-color: rgb(251, 250, 248); color: rgb(51, 51, 51); font-family: Calibri; font-weight: bold;">def list_sum(num_list):</span></div><div><span style="font-size: 10pt; background-color: rgb(251, 250, 248); color: rgb(51, 51, 51); font-family: Calibri; font-weight: bold;">    if len(num_list) == 1:</span></div><div><span style="font-size: 10pt; background-color: rgb(251, 250, 248); color: rgb(51, 51, 51); font-family: Calibri; font-weight: bold;">        return num_list[0]</span></div><div><span style="font-size: 10pt; background-color: rgb(251, 250, 248); color: rgb(51, 51, 51); font-family: Calibri; font-weight: bold;">    else:</span></div><div><span style="font-size: 10pt; background-color: rgb(251, 250, 248); color: rgb(51, 51, 51); font-family: Calibri; font-weight: bold;">        return num_list[0] + list_sum(num_list[1:])</span></div><div><span style="font-size: 10pt; background-color: rgb(251, 250, 248); color: rgb(51, 51, 51); font-family: Calibri; font-weight: bold;">print(list_sum([1,3,5,7,9]))</span></div></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><font style="font-size: 18pt;"><span style="font-size: 18pt; color: rgb(28, 51, 135); font-weight: bold;">递归中的动态规划</span></font></div><div><br/></div><div><span style="font-size: 18px; font-family: SimSun;">在上面的数字三角形中寻找一条从顶部到底边的路径，使得路径上所经过的数字之和最大。</span></div><div>输入格式：</div><div>    5      //表示三角形的行数    接下来输入三角形</div><div>    7</div><div>    3   8</div><div>    8   1   0</div><div>    2   7   4   4</div><div>    4   5   2   6   5</div><div>    要求输出最大和</div><div>    接下来，我们来分析一下解题思路：</div><div>    首先，肯定得用二维数组来存放数字三角形</div><div>    然后我们用D( r, j) 来表示第r行第 j 个数字(r,j从1开始算)</div><div>    我们用MaxSum(r, j)表示从D(r,j)到底边的各条路径中，最佳路径的数字之和。</div><div>    因此，此题的最终问题就变成了求 MaxSum(1,1)</div><div>    当我们看到这个题目的时候，首先想到的就是可以用简单的递归来解题：</div><div>    D(r, j)出发，下一步只能走D(r+1,j)或者D(r+1, j+1)。故对于N行的三角形，我们可以写出如下的递归式：   </div><div style="box-sizing: border-box; padding: 8px; font-size: 12px; border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.14902);"><div><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">if ( r == N)</span></div><div><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">    maxSum(r,j) = D(r, j)</span></div><div><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">else</span></div><div><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">    MaxSum(r,j) = Max{ MaxSum(r + 1, j), MaxSum(r+1, j+1)} + D(r,j)</span></div></div><div><br/></div><div style="box-sizing: border-box; padding: 8px; font-size: 12px; border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.14902);"><div><ol start="1"><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">#include &lt;iostream&gt;    </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">#include &lt;algorithm&gt;   </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">#define MAX 101    </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">using namespace std;   </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">int D[MAX][MAX];    </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">int n;    </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">int MaxSum(int i, int j){      </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">    if(i==n)    </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">        return D[i][j];      </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">    int x = MaxSum(i+1,j);      </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">    int y = MaxSum(i+1,j+1);      </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">    return max(x,y)+D[i][j];    </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">}  </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">int main(){      </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">    int i,j;      </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">    cin &gt;&gt; n;      </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">    for(i=1;i&lt;=n;i++)     </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">        for(j=1;j&lt;=i;j++)          </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">            cin &gt;&gt; D[i][j];      </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">    cout &lt;&lt; MaxSum(1,1) &lt;&lt; endl;    </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">}        </span></li></ol></div></div><div><span style="font-size: 18px; font-family: SimSun;">对于如上这段递归的代码，当我提交到POJ时，会显示如下结果：</span><span style="line-height: 1.45;">  </span><img src="递归算法_files/Image.png" type="image/png" data-filename="Image.png" style="line-height: 1.45;"/></div><div><span style="font-size: 18px; font-family: SimSun;">    对的，</span><font style="font-size: 16pt;"><span style="font-size: 16pt; color: rgb(173, 0, 0); font-family: SimSun; font-weight: bold;">代码运行超时了</span></font><span style="font-size: 18px; font-family: SimSun;">，为什么会超时呢？</span></div><div><span style="font-size: 18px; font-family: SimSun;">因为</span><font style="font-size: 16pt;"><span style="font-size: 16pt; color: rgb(173, 0, 0); font-family: SimSun; font-weight: bold;">我们重复计算</span></font><span style="font-size: 18px; font-family: SimSun;">了，当我们在进行递归时，计算机帮我们计算的过程如下图：</span></div><div>    <img src="递归算法_files/20150811140840233.png" type="image/png" data-filename="20150811140840233.png" width="330"/></div><div>就拿第三行数字1来说，当我们计算从第2行的数字3开始的MaxSum时会计算出从1开始的MaxSum，当我们计算从第二行的数字8开始的MaxSum的时候又会计算一次从1开始的MaxSum，也就是说有重复计算。这样就浪费了大量的时间。也就是说如果采用递规的方法，深度遍历每条路径，存在大量重复计算。则时间复杂度为 2的n次方,对于 n = 100 行，肯定超时。</div><div><br/></div><div><font style="font-size: 16pt;"><span style="font-size: 16pt; color: rgb(173, 0, 0); font-weight: bold;">解：</span></font></div><div>每算出一个MaxSum(r,j)就保存起来，下次用到其值的时候直接取用，则可免去重复计算。那么可以用n方的时间复杂度完成计算。因为三角形的数字总数是 n(n+1)/2</div><div><br/></div><div>据这个思路，我们就可以将上面的代码进行改进，使之成为<font style="font-size: 12pt;"><span style="font-size: 12pt; color: rgb(173, 0, 0); font-weight: bold;">记忆递归型的动态规划程序</span></font>： </div><div style="box-sizing: border-box; padding: 8px; font-size: 12px; border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.14902);"><div><ol start="1"><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">#include &lt;iostream&gt;    </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">#include &lt;algorithm&gt;   </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">using namespace std;  </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">   </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">#define MAX 101  </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">    </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">int D[MAX][MAX];      </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">int n;    </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">int maxSum[MAX][MAX];  </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">   </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">int MaxSum(int i, int j){        </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">    if( maxSum[i][j] != -1 )           </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">        return maxSum[i][j];        </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">    if(i==n)     </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">        maxSum[i][j] = D[i][j];       </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">    else{      </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">        int x = MaxSum(i+1,j);         </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">        int y = MaxSum(i+1,j+1);         </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">        maxSum[i][j] = max(x,y)+ D[i][j];       </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">    }       </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">    return maxSum[i][j];   </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">}   </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">int main(){      </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">    int i,j;      </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">    cin &gt;&gt; n;      </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">    for(i=1;i&lt;=n;i++)     </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">        for(j=1;j&lt;=i;j++) {         </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">            cin &gt;&gt; D[i][j];         </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">            maxSum[i][j] = -1;     </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">        }      </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">    cout &lt;&lt; MaxSum(1,1) &lt;&lt; endl;   </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">}   </span></li></ol></div></div><div><br/></div><div><font style="font-size: 14pt;"><span style="font-size: 14pt; color: rgb(173, 0, 0); font-weight: bold;">递归总是需要使用大量堆栈上的空间，很容易造成栈溢出，我们现在就要考虑如何把递归转换为递推，让我们一步一步来完成这个过程。</span></font></div><div><span style="font-size: 18px; font-family: SimSun;">我们首先需要计算的是最后一行，因此可以把最后一行直接写出，如下图：</span></div><div>    <img src="递归算法_files/Image [1].png" type="image/png" data-filename="Image.png" width="410"/></div><div><br/></div><div><span style="font-size: 18px; font-family: SimSun;">现在开始分析倒数第二行的每一个数，现分析数字2，2可以和最后一行4相加，也可以和最后一行的5相加，但是很显然和5相加要更大一点，结果为7，我们此时就可以将7保存起来，然后分析数字7，7可以和最后一行的5相加，也可以和最后一行的2相加，很显然和5相加更大，结果为12，因此我们将12保存起来。以此类推。。我们可以得到下面这张图：</span></div><div>    <img src="递归算法_files/Image [2].png" type="image/png" data-filename="Image.png" width="410"/></div><div><span style="font-size: 18px; font-family: SimSun;">同样的道理分析倒数第三行和倒数第四行，最后分析第一行，我们可以依次得到如下结果：</span></div><div><img src="递归算法_files/Image [3].png" type="image/png" data-filename="Image.png" width="438"/></div><div><font style="font-size: 16pt;"><span style="font-size: 16pt; color: rgb(173, 0, 0); font-weight: bold;">写出如下的递推型动态规划程序：</span></font></div><div><br/></div><div style="box-sizing: border-box; padding: 8px; font-size: 12px; border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.14902);"><div><ol start="1"><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">#include &lt;iostream&gt;    </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">#include &lt;algorithm&gt;   </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">using namespace std;   </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">  </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">#define MAX 101    </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">  </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">int D[MAX][MAX];     </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">int n;    </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">int maxSum[MAX][MAX];   </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">int main(){      </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">    int i,j;      </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">    cin &gt;&gt; n;      </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">    for(i=1;i&lt;=n;i++)     </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">        for(j=1;j&lt;=i;j++)          </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">            cin &gt;&gt; D[i][j];     </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">    for( int i = 1;i &lt;= n; ++ i )       </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">        maxSum[n][i] = D[n][i];     </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">    for( int i = n-1; i&gt;= 1;  --i )       </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">      for( int j = 1; j &lt;= i; ++j )           </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">        maxSum[i][j] = max(maxSum[i+1][j],maxSum[i+1][j+1]) </span><span style="background-color: rgb(251, 250, 248); font-size: 10pt; color: rgb(173, 0, 0); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace; font-weight: bold;">+ D[i][j]</span><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(173, 0, 0); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace; font-weight: bold;">;      </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">    cout &lt;&lt; maxSum[1][1] &lt;&lt; endl;    </span></li><li><span style="background-color: rgb(251, 250, 248); font-size: 12px; color: rgb(51, 51, 51); font-family: Monaco, Menlo, Consolas, 'Courier New', monospace;">}   </span></li></ol></div></div><div><br/></div><div><br/></div><div><span style="font-size: 18px; font-family: SimSun;">其实完全没必要用二维maxSum数组存储每一个MaxSum(r,j),只要从底层一行行向上递推，那么只要一维数组maxSum[100]即可,即只要存储一行的MaxSum值就可以</span></div><div><span style="font-size: 18px; font-family: SimSun;">过程：</span></div><div>    <img src="递归算法_files/Image [4].png" type="image/png" data-filename="Image.png"/></div><div><br/></div><div><img src="递归算法_files/Image [5].png" type="image/png" data-filename="Image.png"/></div><div><br/></div><div><img src="递归算法_files/Image [6].png" type="image/png" data-filename="Image.png"/></div><div><span>接下里的步骤就按上图的过程一步一步推导就可以了。进一步考虑，我们甚至可以连maxSum数组都可以不要，直接用D的第n行直接替代maxSum即可。但是这里需要强调的是：虽然节省空间，但是时间复杂度还是不变的。</span></div><div style="box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, &quot;Courier New&quot;, monospace; font-size: 12px; color: rgb(51, 51, 51); border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.14902); background-position: initial initial; background-repeat: initial initial;-en-codeblock:true;"><div><ol start="1"><li>#include &lt;iostream&gt;    </li><li>#include &lt;algorithm&gt;   </li><li>using namespace std;   </li><li>  </li><li>#define MAX 101    </li><li>  </li><li>int D[MAX][MAX];    </li><li>int n;   </li><li>int * maxSum;   </li><li>  </li><li>int main(){      </li><li>    int i,j;      </li><li>    cin &gt;&gt; n;      </li><li>    for(i=1;i&lt;=n;i++)     </li><li>        for(j=1;j&lt;=i;j++)          </li><li>            cin &gt;&gt; D[i][j];     </li><li>    maxSum = D[n]; //maxSum指向第n行      </li><li>    for( int i = n-1; i&gt;= 1;  --i )       </li><li>        for( int j = 1; j &lt;= i; ++j )         </li><li>            maxSum[j] = max(maxSum[j],maxSum[j+1]) + D[i][j];      </li><li>    cout &lt;&lt; maxSum[1] &lt;&lt; endl;    </li><li>}  </li></ol></div></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div></span>
</div></body></html> 